#include <algorithm>
#include <iostream>
#include "gtest/gtest.h"
#include "PriorityQueue.h"

TEST(Heap, PushAndPop) {
	PriorityQueue<int> queue;
	ASSERT_EQ(0, queue.size());
	queue.push(4);
	ASSERT_EQ(1, queue.size());
	int x;
	ASSERT_TRUE(queue.pop(x));
	ASSERT_EQ(4, x);
	ASSERT_EQ(0, queue.size());
}

TEST(Heap, HeapIntSort) {
	int n = 100;
	vector<int> t(n);
	for (int i = 0; i < n; ++i)
		t[i] = i;
	
	ASSERT_EQ(t.size(), n);
	for (int i = 0; i < n; ++i)
		ASSERT_EQ(t[i], i);
	
	std::random_shuffle(t.begin(), t.end());

	PriorityQueue<int> queue(t);
	vector<int> result;
	int e;
	while (queue.pop(e)) 
		result.push_back(e);
	
	ASSERT_EQ(result.size(), n);
	for (int i = 0; i < n; ++i)
		ASSERT_EQ(result[i], i);
}

TEST(Heap, HeapStringSort) {
	int n = 26;
	vector<string> t(n);
	for (int i = 0; i < n; ++i)
		t[i] = string(1, 'a'+i);
	
	ASSERT_EQ(t.size(), n);
	for (int i = 0; i < n; ++i)
		ASSERT_EQ(t[i], string(1, 'a'+i));
	
	std::random_shuffle(t.begin(), t.end());

	PriorityQueue<string> queue(t);
	vector<string> result;
	string e;
	while (queue.pop(e)) 
		result.push_back(e);
	
	ASSERT_EQ(result.size(), n);
	for (int i = 0; i < n; ++i)
		ASSERT_EQ(result[i], string(1, 'a'+i));
}

